\documentclass{ctexart}
\bibliographystyle{IEEEtran}
\usepackage{url}
\usepackage{graphicx}
\usepackage{algorithm,algorithmic}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tikz}
\pagestyle{plain}
\title{Bellman-Ford算法的实现}
\author{张祺\\信息与计算科学 2101  3210104145}
\date{2022年12月8日}
\begin{document}
\maketitle

\section{设计思路}
Bellman-Ford算法需要进行$V_{num}-1$次松弛，而每次循环开始时需要拷贝上一次的结果，避免在本次循环操作中引起混乱。

\section{测试样例}
\subsection{稠密图，顶点数为1000，边数为1000000，取n=0,500,950}
所耗时间为：8.06889;所耗时间为：8.39047;所耗时间为：8.12364。
\subsection{稀疏图，顶点数为1000，边数为1000,取n=0,500,950}
所耗时间为：0.006804;所耗时间为：0.006585;所耗时间为：0.006455。
\subsection{稀疏图，顶点数为1000，边数接近10000,取n=0,500,950}
所耗时间为：0.111353;所耗时间为：0.111202;所耗时间为：0.110651。
\subsection{稀疏图，顶点数为1000，边数接近100000,取n=0,500,950}
所耗时间为：1.00396;所耗时间为：1.00666;所耗时间为：1.04152。
\subsection{稠密图，顶点数为2000，边数为4000000，取n=0,500,950}
所耗时间为：63.1662;所耗时间为：63.5843;所耗时间为：66.9357。
\subsection{结果说明}
在顶点数和边数确定时，改变源点的取值不会大幅度地改变Bellman-Ford算法的所需时间;固定顶点数后，边数放大十倍，所需时间近似放大十倍;稠密图中，将顶点数放大2倍，所需时间放大倍率也近似为8。
\subsection{结论}
试验结果说明，Bellman-Ford算法的时间复杂度为O(VE)，且随着源点的改变，算法效率改变较小。

\end{document}
